package leetcode.code0143;

import leetcode.helper.HelpDebug;
import leetcode.helper.tree.ListNode;

public class Solution {
	public void reorderList(ListNode head) {
		int size = 0;
		ListNode p = head;
		while (p != null) {
			p = p.next;
			size++;
		}
		if (size == 1)
			return;
		int move = (size & 1) == 0 ? (size >> 1) - 1 : size >> 1;
		p = head;
		while (move > 0) {
			p = p.next;
			move--;
		}
		ListNode p1 = p.next;
		p.next = null;
		p = new ListNode();
		ListNode p2 = null;
		while (p1 != null) {
			p2 = p1.next;
			p1.next = p.next;
			p.next = p1;
			p1 = p2;
		}
		p1 = head;
		p2 = p.next;
		p = new ListNode();
		p = head;
		while (p1 != null) {
			p1 = p1.next;
			p.next = p2;
			p2 = p2 != null ? p2.next : null;
			p = p.next;
			p.next = p1;
		}
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.reorderList(ListNode.set(HelpDebug.str2array3("[1,2,3,4]")));
	}
}
